package _数据结构系列._单调队列;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/11 20:52
 * <p>
 * 功能描述: 面试题59 - I和239是一个题
 */
public class Summary_0239 {
    public static void main(String[] args) {
        Solution test = new Solution();
        int[] nums = {1,3,-1,-3,5,3,6,7};
        test.maxSlidingWindow(nums,3);

    }
}

class Solution {

    private Deque<Integer> data = new ArrayDeque<>();

    public void push(int n) {
        while (!data.isEmpty() && data.getLast() < n)
            data.removeLast();
        data.addLast(n);
    }

    int max() {
        return data.getFirst();
    }

    void pop(int n) {
        if (!data.isEmpty() && data.getFirst() == n)
            data.removeFirst();
    }

    public int[] maxSlidingWindow(int[] nums, int k) {

        int n = nums.length;
        if (n * k == 0) return new int[0];
        Solution window = new Solution();
        int[] res = new int[nums.length - k + 1];
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i < k - 1) { //先填满窗口的前 k - 1
                window.push(nums[i]);
            } else { // 窗口向前滑动
                window.push(nums[i]);
                res[index++] = window.max();
                window.pop(nums[i - k + 1]);
            }
        }
        return res;

    }

}
